package krypto.exercise;

import java.math.BigInteger;

public class EEuclid {
	public static EEResultBigInteger calc (BigInteger a, BigInteger b) throws Exception {
		//		LocalTimer lt = new LocalTimer();
		EEResultBigInteger result = new EEResultBigInteger();

		//This method returns -1, 0 or 1 as this BigInteger is numerically less than, equal to, or greater than val.
		if ((a.compareTo(b)) < 0) {
			System.out.println("a should be bigger or equal to b");
			throw new KryptoException("a should be bigger or equal to b");
		}

		BigInteger L = a;
		BigInteger R = b;
		BigInteger x = BigInteger.valueOf(1);
		BigInteger y = BigInteger.valueOf(0);
		BigInteger X = BigInteger.valueOf(0);
		BigInteger Y = BigInteger.valueOf(1);

		BigInteger q;
		BigInteger t;
		BigInteger u;
		BigInteger v;

		do {
			q = L.divide(R);
			t = R;
			R = L.mod(R);
			L = t;
			u = X;
			v = Y;
			X = x.subtract(q.multiply(X));
			Y = y.subtract(q.multiply(Y));
			x = u;
			y = v;

		} while ( R.compareTo(BigInteger.valueOf(0)) != 0);

		result.L = L;
		result.x = x;
		result.y = y;

		//		lt.stop();		
		return result;
	}
	
	public static void main(String[] args) throws Exception {
		
		EEResultBigInteger eEResultBigInteger = EEuclid.calc(BigInteger.valueOf(47),BigInteger.valueOf(4));
		System.out.println(eEResultBigInteger.L + " " + eEResultBigInteger.x + " " + eEResultBigInteger.y);
		
		eEResultBigInteger = EEuclid.calc(BigInteger.valueOf(59),BigInteger.valueOf(3));
		System.out.println(eEResultBigInteger.L + " " + eEResultBigInteger.x + " " + eEResultBigInteger.y);
		
		eEResultBigInteger = EEuclid.calc(BigInteger.valueOf(187),BigInteger.valueOf(3));
		System.out.println(eEResultBigInteger.L + " " + eEResultBigInteger.x + " " + eEResultBigInteger.y);
	}
}